package org.xingole.leetcode.dp;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.com/problems/valid-parenthesis-string/description/">
 * Problem Description
 * </a>
 */
public class ValidParenthesisString {
    /**
     * 
     * @param s a string containing only three types of characters '(', ')', and '*'
     * @return true if s is valid.
     */
    public boolean checkValidString(String s) {
        int n = s.length();

        boolean[][] dp = new boolean[n][n];
        // base case
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                dp[i][i] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            char c1 = s.charAt(i - 1);
            char c2 = s.charAt(i);
            dp[i - 1][i] = 
                (c1 == '(' || c1 == '*') &&
                (c2 == ')' || c2 == '*');
        }

        // state transfer
        for (int i = n - 3; i >= 0; --i) {
            char c1 = s.charAt(i);

            for (int j = i + 2; j < n; j++) {
                char c2 = s.charAt(j);

                if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
                    dp[i][j] = dp[i + 1][j - 1];
                }

                for (int k = i; k < j && !dp[i][j]; k++) {
                    dp[i][j] = dp[i][k] && dp[k + 1][j];
                }
            }
        }

        return dp[0][n - 1];
    }

    public boolean checkValidString2(String s) {
        Deque<Integer> leftStack     = new LinkedList<>();
        Deque<Integer> asteriskStack = new LinkedList<>();

        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftStack.push(i);
            } else if (c == '*') {
                asteriskStack.push(i);
            } else {
                if (!leftStack.isEmpty()) {
                    leftStack.pop();
                } else if (!asteriskStack.isEmpty()) {
                    asteriskStack.pop();
                } else {
                    return false;
                }
            }
        }

        while (!leftStack.isEmpty() && !asteriskStack.isEmpty()) {
            int leftIndex     = leftStack.pop();
            int asteriskIndex = asteriskStack.pop();

            if (leftIndex > asteriskIndex) {
                return false;
            }
        }

        return leftStack.isEmpty();
    }
}
